Konkurs programistyczny
Limit pamięci: 64 MB
Bajtazar przygotowuje się do udziału w finale indywidualnego konkursu
programistycznego.
W ramach przygotowań bardzo wnikliwie przeczytał regulamin konkursu, jak
również zasady organizacji zawodów, i dowiedział się, że w finale będzie
do rozwiązania dokładnie zadań, a każde zadanie będzie należało do
jednej spośród dziedzin.
Może się zdarzyć więcej niż jedno zadanie z danej dziedziny.
Bajtazar zna dobrze wszystkich uczestników finału i dla każdego zawodnika
wie, jakie są jego kompetencje w poszczególnych dziedzinach.
Kompetencja w dziedzinie wyraża się zawsze dodatnią liczbą całkowitą; wyższa liczba
oznacza wyższe umiejętności.
Każde zadanie w konkursie będzie miało pewną trudność, określoną dodatnią
liczbą całkowitą.
Bajtazar zakłada, że dane zadanie rozwiążą tylko ci zawodnicy, których
kompetencja jest nie mniejsza niż trudność danego zadania.
Za zadanie, które zrobi, zawodnik otrzyma liczbę punktów równą różnicy
swojej kompetencji w danej dziedzinie i trudności zadania.
Ostateczny ranking jest ustalany przede wszystkim według liczby rozwiązanych
zadań (tj. zawodnik, który zrobił więcej zadań, jest zawsze wyżej
w rankingu niż ten, który zrobił mniej), a wśród zawodników o tej samej
liczbie zadań - według punktacji (im więcej punktów, tym zawodnik jest
wyżej sklasyfikowany).
Bajtazar, zamiast porządnie trenować do konkursu, zaczął zastanawiać
się, czy istnieje taki dobór zadań, przy którym wygra.
Nie umie jednak tego stwierdzić (a poza tym chciałby może jednak
jeszcze trochę potrenować), więc poprosił Cię o pomoc.
Możesz założyć, że ewentualne remisy są rozstrzygane na niekorzyść
Bajtazara.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita
() oznaczająca liczbę zestawów testowych.
W kolejnych wierszach znajdują się opisy poszczególnych zestawów.
W pierwszym wierszu opisu każdego zestawu znajdują się trzy dodatnie liczby
całkowite , i (,
), pooddzielane pojedynczymi odstępami
i oznaczające kolejno liczby zadań, zawodników oraz dziedzin, do których
należą zadania.
Dalej następuje wierszy opisujących poszczególnych zawodników.
W -tym z nich znajduje się liczb całkowitych z przedziału
, pooddzielanych pojedynczymi odstępami, oznaczających
kompetencje -tego zawodnika w kolejnych dziedzinach.
Pierwszy spośród tych wierszy opisuje umiejętności Bajtazara.
Wyjście
Na standardowe wyjście należy wypisać dokładnie wierszy, po jednym
dla każdego zestawu testowego.
Odpowiedzią dla każdego zestawu jest jedno słowo
TAK lub NIE, oznaczające,
czy Bajtazar ma szansę zwyciężyć w konkursie.
Przykład
Dla danych wejściowych:
2
3 6 5
70 100 100 70 100
205 180 70 200 150
180 200 30 25 45
75 45 80 180 180
120 10 120 90 10
15 110 135 150 210
2 2 2
12 12
20 20
poprawną odpowiedzią jest:
TAK
NIE
Wyjaśnienie do przykładu:
Dla pierwszego testu przykładowym zestawem zadań, przy którym Bajtazar zwycięży w finale,
jest: zadanie z pierwszej kategorii o trudności 5, zadanie z drugiej kategorii
o trudności 20 oraz zadanie z trzeciej kategorii o trudności 75.
Wtedy końcowa tabela wygląda następująco:
- Bajtazar (zawodnik 1): 3 zadania, 170 punktów
- Zawodnik 6: 3 zadania, 160 punktów
- Zawodnik 4: 3 zadania, 100 punktów
- Zawodnik 2: 2 zadania, 360 punktów
- Zawodnik 3: 2 zadania, 355 punktów
- Zawodnik 5: 2 zadania, 160 punktów
Dla drugiego testu nie istnieje odpowiedni dobór zadań.
Autor zadania: Jakub Onufry Wojtaszczyk.